#include <gtest/gtest.h>

#include <algorithm>
#include <cmath>
#include <iostream>

#include "algorithm/backtrack/include/aroundArea.h"
#include "algorithm/common/include/utils.h"
#include "algorithm/datastruct/include/LRUCache.h"
#include "algorithm/datastruct/include/TreeNode.h"
#include "algorithm/datastruct/include/TreeOperator.h"
#include "algorithm/datastruct/include/bfs_tree.h"
#include "algorithm/datastruct/include/maxSlidingWindow.h"
#include "algorithm/datastruct/include/trap.h"
TEST(TreeBFS, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(3);
    TreeNode *node2 = new TreeNode(4);
    TreeNode *node3 = new TreeNode(5);
    TreeNode *node4 = new TreeNode(6);
    TreeNode *node5 = new TreeNode(7);

    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    std::vector<int> bfs_list = BFSTreeWithValue(node1);
    int a[] = {3, 4, 5, 6, 7};
    EXPECT_TRUE(valuesIsSame(bfs_list.data(), a, 5));

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}
TEST(TreeIsSymmetric, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(2);
    TreeNode *node4 = new TreeNode(3);
    TreeNode *node5 = new TreeNode(4);
    TreeNode *node6 = new TreeNode(4);
    TreeNode *node7 = new TreeNode(3);

    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node3->left = node6;
    node3->right = node7;
    EXPECT_TRUE(isSymmetric(node1));
    node7->val = 8;
    EXPECT_FALSE(isSymmetric(node1));
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
}

TEST(TreeIsSymmetric1, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(2);
    TreeNode *node4 = new TreeNode(3);
    TreeNode *node5 = new TreeNode(3);

    node1->left = node2;
    node1->right = node3;
    node2->left = nullptr;
    node2->right = node4;
    node3->left = node5;
    node3->right = nullptr;
    EXPECT_TRUE(isSymmetric(node1));
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TreeIsSameTree, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(2);

    TreeNode *node4 = new TreeNode(1);
    TreeNode *node5 = new TreeNode(2);
    TreeNode *node6 = new TreeNode(3);

    node1->left = node2;
    node2->right = node3;

    node4->right = node5;
    node5->left = node6;
    EXPECT_FALSE(isSameTree(node1, node4));

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TreeIsSubTree, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(4);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);

    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node6 = new TreeNode(6);
    TreeNode *node7 = new TreeNode(7);
    TreeNode *node8 = new TreeNode(8);
    TreeNode *node9 = new TreeNode(9);

    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;

    node3->left = node6;
    node3->right = node7;
    node4->left = node8;
    node4->right = node9;

    TreeNode *node10 = new TreeNode(4);
    TreeNode *node11 = new TreeNode(8);
    TreeNode *node12 = new TreeNode(9);
    node10->left = node11;
    node10->right = node12;
    EXPECT_TRUE(isContainSubTree(node1, node10));
    //   node11->val=20;
    //   EXPECT_FALSE(isContainSubTree(node1,node10));
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
    delete node8;
    delete node9;
    delete node10;
    delete node11;
    delete node12;
}

TEST(TreeMirror, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(4);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);

    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node6 = new TreeNode(6);
    TreeNode *node7 = new TreeNode(7);

    node1->left = node2;
    node1->right = node3;

    node2->left = node4;
    node2->right = node5;

    node3->left = node6;
    node3->right = node7;

    TreeNode *tmp = mirrorTree(node1);
    std::vector<int> bs = BFSTreeWithValue(node1);
    int res[] = {4, 3, 2, 7, 6, 5, 4};
    EXPECT_TRUE(valuesIsSame(bs.data(), res, bs.size()));

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
}

TEST(IsBSTTree, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(5);
    TreeNode *node2 = new TreeNode(1);
    TreeNode *node3 = new TreeNode(4);

    TreeNode *node4 = new TreeNode(3);
    TreeNode *node5 = new TreeNode(6);

    node1->left = node2;
    node1->right = node3;

    node3->left = node4;
    node3->right = node5;

    EXPECT_FALSE(isValidBST(node1));

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(IsMinDepth1, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(3);
    TreeNode *node2 = new TreeNode(9);
    TreeNode *node3 = new TreeNode(20);

    TreeNode *node4 = new TreeNode(15);
    TreeNode *node5 = new TreeNode(7);

    node1->left = node2;
    node1->right = node3;

    node3->left = node4;
    node3->right = node5;

    EXPECT_EQ(minDepth(node1), 2);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(IsMinDepth2, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(2);
    TreeNode *node2 = new TreeNode(3);
    TreeNode *node3 = new TreeNode(4);
    TreeNode *node4 = new TreeNode(5);
    TreeNode *node5 = new TreeNode(6);

    node1->right = node2;
    node2->right = node3;
    node3->right = node4;
    node4->right = node5;

    EXPECT_EQ(minDepth(node1), 5);
    EXPECT_EQ(minDepthWithBFS(node1), 5);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(CommonTreeParent, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(6);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(8);
    TreeNode *node4 = new TreeNode(0);
    TreeNode *node5 = new TreeNode(4);
    TreeNode *node6 = new TreeNode(7);
    TreeNode *node7 = new TreeNode(9);
    TreeNode *node8 = new TreeNode(3);
    TreeNode *node9 = new TreeNode(5);

    node1->left = node2;
    node1->right = node3;

    node2->left = node4;
    node2->right = node5;

    node5->left = node8;
    node5->right = node9;

    node3->left = node6;
    node3->right = node7;

    std::vector<TreeNode *> p_path = getPath(node1, node5);
    std::vector<TreeNode *> q_path = getPath(node1, node4);
    std::vector<int> p_values = std::vector<int>(p_path.size());
    std::vector<int> q_values = std::vector<int>(q_path.size());

    std::transform(p_path.begin(), p_path.end(), p_values.begin(),
                   [](TreeNode *node) { return node->val; });
    std::transform(q_path.begin(), q_path.end(), q_values.begin(),
                   [](TreeNode *node) { return node->val; });

    int p_paths[] = {6, 2, 4};
    int q_paths[] = {6, 2, 0};
    EXPECT_TRUE(valuesIsSame(p_values.data(), p_paths, 3));
    EXPECT_TRUE(valuesIsSame(q_values.data(), q_paths, 3));
    TreeNode *node = lowestCommonAncestor(node1, node5, node4);
    EXPECT_EQ(node->val, 2);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
    delete node8;
    delete node9;
}

TEST(SumOfPath, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(5);
    TreeNode *node2 = new TreeNode(4);
    TreeNode *node3 = new TreeNode(8);
    TreeNode *node4 = new TreeNode(11);
    TreeNode *node5 = new TreeNode(13);
    TreeNode *node6 = new TreeNode(4);
    TreeNode *node7 = new TreeNode(7);
    TreeNode *node8 = new TreeNode(2);
    TreeNode *node9 = new TreeNode(1);

    node1->left = node2;
    node1->right = node3;

    node2->left = node4;

    node4->left = node7;
    node4->right = node8;

    node3->left = node5;
    node3->right = node2;

    node6->right = node9;

    bool r = hasPathSum(node1, 22);
    EXPECT_TRUE(r);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
    delete node8;
    delete node9;
}
TEST(TestMaxDepth, BaseGraphTest) {
    Node *node1 = new Node(1);
    Node *node2 = new Node(3);
    Node *node3 = new Node(2);
    Node *node4 = new Node(4);
    Node *node5 = new Node(5);
    Node *node6 = new Node(6);
    node1->children = {node2, node3, node4};
    node2->children = {node5, node6};

    EXPECT_EQ(maxDepth(node1), 3);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestLevelOrder, BaseGraphTest) {
    TreeNode *node1 = new TreeNode(3);
    TreeNode *node2 = new TreeNode(9);
    TreeNode *node3 = new TreeNode(20);
    TreeNode *node4 = new TreeNode(15);
    TreeNode *node5 = new TreeNode(7);
    node1->left = node2;
    node1->right = node3;
    node3->left = node4;
    node3->right = node5;

    auto res = levelOrderRecord(node1);
    vector<vector<int>> truth = {{3}, {9, 20}, {15, 7}};
    EXPECT_TRUE(valuesIsSame(res, truth, 0));

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TestMergeTree, BaseTreeTest) {
    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(3);
    TreeNode *node3 = new TreeNode(2);
    TreeNode *node4 = new TreeNode(5);

    TreeNode *node5 = new TreeNode(2);
    TreeNode *node6 = new TreeNode(1);
    TreeNode *node7 = new TreeNode(3);
    TreeNode *node8 = new TreeNode(4);
    TreeNode *node9 = new TreeNode(7);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;

    node5->left = node6;
    node5->right = node7;
    node6->right = node8;
    node7->right = node9;
    TreeNode *node = mergeTrees(node1, node5);
    std::vector<int> merge_list = BFSTreeWithValue(node);
    vector<int> truth = {3, 4, 5, 5, 4, 7};
    EXPECT_TRUE(valuesIsSame(merge_list, truth));

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
    delete node8;
    delete node9;
}

TEST(TestBinaryTreePaths, BaseTreeTest) {

    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    node1->left = node2;
    node1->right = node3;
    node3->left = node4;
    auto res = binaryTreePaths(node1);
    vector<string> truth = {"1->2", "1->3->4"};
    for (int i = 0; i < truth.size(); i++) {
        EXPECT_EQ(truth[i], res[i]);
    }
    delete node1;
    delete node2;
    delete node3;
    delete node4;
}

TEST(TestBinaryMaxPathsSum, BaseTreeTest) {

    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    node1->left = node2;
    node1->right = node3;
    node3->left = node4;
    auto res = binaryMaxTreePathsSum(node1);
    EXPECT_EQ(res, 8);
    delete node1;
    delete node2;
    delete node3;
    delete node4;
}

TEST(TestFlatten, BaseTreeTest) {

    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node6 = new TreeNode(6);
    node1->left = node2;
    node1->right = node5;
    node2->left = node3;
    node2->right = node4;
    node5->right = node6;
    flatten(node1);

    auto res = travelTree(node1);
    vector<int> truth = {1, 2, 3, 4, 5, 6};
    for (int i = 0; i < res.size(); i++) {
        EXPECT_EQ(res[i], truth[i]);
    }
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestKthLargest, BaseTreeTest) {

    TreeNode *node1 = new TreeNode(5);
    TreeNode *node2 = new TreeNode(3);
    TreeNode *node3 = new TreeNode(6);
    TreeNode *node4 = new TreeNode(2);
    TreeNode *node5 = new TreeNode(4);
    TreeNode *node6 = new TreeNode(1);
    node1->left = node2;
    node1->right = node3;
    node2->left = node4;
    node2->right = node5;
    node4->left = node6;
    EXPECT_EQ(kthLargest(node1, 3), 4);
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestLRUCache, BaseTreeTest) {
    LRUCache *lRUCache = new LRUCache(2);
    lRUCache->put(1, 1);
    lRUCache->put(2, 2);
    lRUCache->get(1);
    lRUCache->put(3, 3);
    lRUCache->get(2);
    lRUCache->put(4, 4);
    lRUCache->get(1);
    lRUCache->get(3);
    lRUCache->get(4);

    delete lRUCache;
}

TEST(TestWidthOfBinaryTree, BaseTreeTest) {
    TreeNode *root = new TreeNode(1);
    TreeNode *node1 = new TreeNode(3);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(5);
    TreeNode *node4 = new TreeNode(9);
    TreeNode *node5 = new TreeNode(6);
    TreeNode *node6 = new TreeNode(7);
    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node3->left = node5;
    node1->right = node2;
    node2->right = node4;
    node4->left = node6;

    EXPECT_EQ(widthOfBinaryTree(root), 7);
    delete root;
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
}

TEST(TestTrap, BaseTreeTest) {
    std::vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    EXPECT_EQ(trap(height), 6);
    height = {4, 2, 0, 3, 2, 5};
    EXPECT_EQ(trap(height), 9);
}

TEST(TestMaxPathSum, BaseTreeTest) {

    TreeNode *node1 = new TreeNode(1);
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3);
    node1->left = node2;
    node1->right = node3;
    EXPECT_EQ(dfsMaxPathSum(node1), 4);
    node1->val = -10;
    node2->val = 9;
    node3->val = 20;
    TreeNode *node4 = new TreeNode(15);
    TreeNode *node5 = new TreeNode(7);
    node3->left = node4;
    node3->right = node5;
    EXPECT_EQ(dfsMaxPathSum(node1), 25);
    EXPECT_EQ(maxPathSum(node1), 42);

    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
}

TEST(TestMaxSlidingWindow, BaseTreeTest) {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    auto res = maxSlidingWindow(nums, 3);
    vector<int> truth = {3, 3, 5, 5, 6, 7};
    EXPECT_TRUE(valuesIsSame(res, truth));
    nums = {1, -1};
    truth = {1, -1};
    res = maxSlidingWindow(nums, 1);
    EXPECT_TRUE(valuesIsSame(res, truth));
    nums = {7, 2, 4};
    res = maxSlidingWindow(nums, 2);
    truth = {7, 4};
    EXPECT_TRUE(valuesIsSame(res, truth));
}

TEST(TestConvertBST, BaseTreeTest) {
    TreeNode *node = new TreeNode(6);
    TreeNode *node1 = new TreeNode(5);
    TreeNode *node2 = new TreeNode(7);
    node->left = node1;
    node->right = node2;
    auto res = convertBST(node);
    auto bst = travelTree(node);
    for (auto e : bst)
        std::cout << "e = " << e << "\n";
    delete node;
    delete node1;
    delete node2;
}
